#include <iostream>
#include <vector>
#include <string>
#include "Vector.hpp"

using namespace std;

class Solution
{
private:
    const vector<string> keypad = {"","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.empty())
            return {};
        if (digits.size() == 1)
        {
            vector<string> result;
            for (char c : keypad[digits[0] - '0'])
            {
                result.push_back(string(1, c));
            }
            return result;
        }
        else
        {
            string temp = keypad[digits[0] - '0'];
            vector<string> res = letterCombinations(digits.substr(1));
            vector<string> result;
            for (char s : temp)
            {
                for (string r : res)
                {
                    result.push_back(s + r);
                }
            }
            return result;
        }
    }
};

int main()
{
    string nums = "23";
    Solution sol;
    vector<string> res = sol.letterCombinations(nums);
    PrintVector(res);
    return 0;
}
